package developer.算法.二叉树.二叉树中序遍历;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author zhangyongkang
 * @time 2024/6/17 20:23
 * @description 给定一个二叉树的根节点 root ，返回 它的 中序（LDR） 遍历 。
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 * 示例 2：
 * <p>
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：root = [1]
 * 输出：[1]
 */
public class Solution_self {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     * <p>
     * <p>
     * 1
     * 2       3
     * 8  1     4  5
     */
    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        TreeNode rootNode = new TreeNode(1, new TreeNode(2, new TreeNode(8), new TreeNode(1)), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
        List<Integer> result = new ArrayList<>();
        solution.order(rootNode, result);
        result.forEach(System.out::println);
    }

    static class Solution {


        public void order(TreeNode rootNode, List<Integer> result) {
            if (rootNode == null) return;
            order(rootNode.left, result);
            result.add(rootNode.val);
            order(rootNode.right, result);
        }

    }

    static class Solution4 {

        public void order(TreeNode rootNode, List<Integer> result) {
            Stack<TreeNode> stack = new Stack<>();
            while (rootNode != null || !stack.isEmpty()) {
                while (rootNode != null) {
                    stack.push(rootNode);
                    rootNode = rootNode.left;
                }
                TreeNode node = stack.pop();
                result.add(node.val);
                rootNode = node.right;
            }
        }
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


}
